A Hybrid Variable Neighborhood Search Algorithm (HVNSA) was proposed for solving Long-Term CarPooling Problem (LTCPP), which reduced the number of vehicle trips by matching the users with the same destination. Firstly, a comprehensive and accurate mathematical model of LTCPP was built. Then all users were assigned to the car pools by the composite distance preference algorithm, the time window and vehicle capacity constraint were verified to obtain the initial carpooling scheme. Secondly, the initial carpooling scheme was optimized by using variable neighborhood search algorithm to obtain the optimal long-term carpooling scheme. The experimental results show that HVNSA can obtain high quality of optimal carpooling scheme within 1 second for 100 people and 200 people instances; at the same time, the algorithm can obtain higher quality of optimal carpooling scheme within 2-4 seconds for the larger-scale instances such as 400 people and 1000 people.

A Preference Matrix based Genetic Algorithm (PMGA) was introduced for solving the Long-Term Car Pooling Problem (LTCPP), and a group of users with both vehicle and the same destination was assigned to the co-generation group to minimize the total travel cost. First, the objective function of calculating the cost of all users was set up, and a long-term car pooling model with constraints of user time window and car capacity was designed. Then based on the characteristics of the model and classic Genetic Algorithm (GA), a preference matrix mechanism was adapted into the crossover and mutation operators to memorize and update the preference information among different users, thus improving the quantity and the quality of feasible solutions. The experimental results show that in the same computing environment, the optimal solution value of 20 solutions obtained by PMGA is the same as that of the exact algorithm when the number of users is less than 200. Moreover, PMGA is remarkable in solution quality when dealing with large size of instances. The proposed algorithm can significantly improve the solution quality of the long-term car pooling problem, and play an important role in reducing vehicle emission and traffic congestion.